package LeetCode;

public class LC_410_SplitArrayLargestSum {

    public static void main(String[] args) {

    }

    static class Solution {
        public int splitArray(int[] nums, int m) {
            int high = 0, low = 0, mid, ans;
            for (int num : nums) {
                high += num;
                low = Math.max(num, low);
            }

            if (m == 1) return high;
            if (m == nums.length) return low;
            ans = high;
            while (low <= high) {
                mid = low + (high - low) / 2;
                boolean flag = true;
                int sum = nums[0];
                int count = 1;
                for (int i = 1; i < nums.length; i++) {
                    sum += nums[i];
                    if (sum > mid) {
                        count++;
                        sum = nums[i];
                    }
                    if (count > m) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    high = mid - 1;
                    ans = mid;
                } else {
                    low = mid + 1;
                }
            }
            return ans;
        }

    }

    static class Solution_2 {
        public int splitArray(int[] nums, int m) {
            long sum = 0;
            int max = 0;
            for (int num : nums) {
                max = Math.max(max, num);
                sum += num;
            }
            return (int) binary(nums, m, sum, max);
        }

        private long binary(int[] nums, int m, long high, long low) {
            long mid = 0;
            while (low + 1 < high) {
                mid = low + (high - low) / 2;
                if (valid(nums, m, mid)) {
                    low = mid;
                } else {
                    high = mid;
                }
            }
            if (valid(nums, m, high))
                return high;
            return low;
        }

        private boolean valid(int[] nums, int m, long target) {
            int sum = 0;
            int count = 0;
            for (int num : nums) {
                sum += num;
                if (sum >= target) {
                    sum = num;
                    count++;
                    if (count == m) {
                        return true;
                    }
                }
            }
            return false;
        }

    }

    static class Solution_3 {
        public static int splitArray(int[] nums, int m) {
            int[] dp = new int[nums.length];
            for (int i = nums.length - 1; i >= 0; i--)
                dp[i] = i == nums.length - 1 ? nums[i] : dp[i + 1] + nums[i];
            for (int im = 2; im <= m; im++) {
                int maxPart = nums.length + 1 - im;
                for (int i = 0; i < maxPart; i++) {
                    dp[i] = Integer.MAX_VALUE;
                    int leftSum = 0;
                    for (int p = i; p < maxPart; p++) {
                        leftSum += nums[p];
                        if (leftSum > dp[i]) break;
                        int val = Math.max(leftSum, dp[p + 1]);
                        if (val < dp[i]) dp[i] = val;
                    }
                    if (im == m) break;
                }
            }
            return dp[0];
        }

    }
}